package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/unique-paths-ii/
 */
public class P63 {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        if(obstacleGrid[0][0]==1 || obstacleGrid[m-1][n-1]==1){
            return 0;                       //起点或者终点有障碍，走不了
        }
        int[][] dp=new int[m+1][n+1];        //dp[i][j]表示从(1,1)走到(i,j)有多少种不同的走法
        //初始化边界上的值,遇到障碍物就停止赋1,后面的都是0
        for(int i=0; i<m && obstacleGrid[i][0]==0;i++){
            dp[i+1][1]=1;
        }
        for(int i=0; i<n && obstacleGrid[0][i]==0;i++){
            dp[1][i+1]=1;
        }
        for(int i=2;i<=m;i++){          //注意从第二行、第二列开始遍历
            for(int j=2;j<=n;j++){
                if(obstacleGrid[i-1][j-1]==1){
                    dp[i][j]=0;         //障碍物，无法到达
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
